import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    // 创建一棵树
    // 创建树的节点
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        // 再创建一个方法

        public TreeNode(char val) {
            this.val = val;
        }
    }
    // 开始创建树
    public TreeNode createTree(){
        TreeNode A= new TreeNode('A');
        TreeNode B= new TreeNode('B');
        TreeNode C= new TreeNode('C');
        TreeNode D= new TreeNode('D');
        TreeNode F= new TreeNode('F');
        TreeNode G= new TreeNode('G');
        TreeNode H= new TreeNode('H');
        TreeNode E= new TreeNode('E');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;   // 返回根节点

    }
    // 树的遍历----> 递归
    // 前序遍历
    public void preOrder(TreeNode root){
        // 1）先打印根节点
        // 递归的结束条件为 数据为空
        if(root == null) return;
        System.out.print(root.val + " ");
        // 2) 再打印左结点
        preOrder(root.left);
        // 3) 再打印右节点
        preOrder(root.right);
    }
    // 中序遍历
    public void inOrder(TreeNode root){
        // 递归的结束条件为 数据为空
        if(root == null) return;
        // 1）先打印左节点
        inOrder(root.left);

        // 2) 再打印根结点
        System.out.print(root.val + " ");

        // 3) 再打印右节点
        inOrder(root.right);
    }
    // 后序遍历
    public void postOrder(TreeNode root){
        // 递归的结束条件为 数据为空
        if(root == null) return;
        // 1）先打印左节点
        postOrder(root.left);
        // 2) 再打印右结点
        postOrder(root.right);
        // 3) 再打印根节点
        System.out.print(root.val + " ");
    }
    // 计算一棵树的节点个数
    public static int usedSize = 0;
    public int size(TreeNode root){
       // root 不为空 就 ++
        if(root == null) {
            return 0;
        }
        usedSize++;
        size(root.left);
        size(root.right);
        return usedSize;
    }
    // 计算一棵树的节点个数
    // 方法二：左树节点+右树节点+1
    public int size2(TreeNode root) {
        if(root == null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    // 获取叶子结点的个数
    public static int leafSize = 0;
    public int getLeafNodeCount(TreeNode root){
        // 1) 左右都为空时，即为 叶子结点 , 就 ++
        if(root == null) return 0;
        if(root.left==null && root.right==null){
            leafSize++;
        }
        // 2) 左树叶子 + 右树叶子 = 整棵树的叶子
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;
    }
    // 获取叶子结点的个数
    // 方法二：
    public int getLeafNodeCount2(TreeNode root){
        // 1) 左右都为空时，即为 叶子结点
        if(root == null) return 0;
        if(root.left==null && root.right==null){
            return 1;
        }
        // 2) 左树叶子 + 右树叶子 = 整棵树的叶子
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    // 计算第 k 层的结点个数
    public int getkLeveNode(TreeNode root,int k){
        if(root == null) return 0;
        if(k == 1){
            return 1;
        }
        return getkLeveNode(root.left,k-1)+getkLeveNode(root.right,k-1);
    }
    // 求一棵树的高度
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        int leftH = getHeight(root.left);
        int rightH= getHeight(root.right);
        return (leftH>rightH?leftH:rightH)+1;
    }
    // 方法二
    public int getHeight2(TreeNode root){
        if(root == null)
            return 0;
        return (getHeight2(root.left)>getHeight2(root.right)?
                getHeight2(root.left):getHeight2(root.right))+1;
    }
    // 查找一棵树是否存在 val 值
    public TreeNode fine(TreeNode root,char val){
        // 1) 先判断根是否为 val 值
        if(root == null)
            return null;
        if(root.val == val)
            return root;
        // 2) 再判断左边
        TreeNode leftL = fine(root.left,val);
        if(leftL!=null)
            return leftL;
        // 3) 最后判断右边
        TreeNode rightR = fine(root.right,val);
        if(rightR!=null)
            return rightR;
        return null;
    }
    // 层次（序）遍历
    public void levelOrder(TreeNode root){
        // 用队列实现
        Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            TreeNode top = queue.poll();
            System.out.println(top.val+" ");
            if(top.left!=null){
                queue.offer(top.left);
            }
            if(top.right!=null){
                queue.offer((top.right));
            }
        }
    }
    //层次（序）遍历
    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(ret == null){
            return ret;
        }
        // 用队列实现
        Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size!=0){
                TreeNode top = queue.poll();
                //System.out.println(top.val+" ");
                //list.add(top.val);
                if(top.left!=null){
                    queue.offer(top.left);
                }
                if(top.right!=null){
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    // 判断一棵树是否为完全二叉树
    public boolean iscompleteTree(TreeNode root){
        // 用到队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 1) 把根放进队列
        if(root!=null){
            queue.offer(root);
        }
        // 2)如果队列不为空，弹出队列的第一个元素 不为空 将根的左右数放进对列，为空就停下
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(root.left);
                queue.offer(root.right);

            } else {
                break;
            }
        }
            // 3） 在队列剩下的元素中，如果全为空，就说明是完全二叉树，只要有一个元素不为空，就说明不是
        while (!queue.isEmpty()){
            TreeNode  tmp = queue.poll();
            if(tmp!=null){
                return false;
            }
        }
        return true;

    }
    // 前序、中序还原二叉树
   /* public  int preindex=0;// 遍历前序的下标
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend){
        // 递归出口 不满足这个条件，就说明没有左右树了
        if(inbegin>inend){
            return null;
        }
        // 先创建根节点
        TreeNode root = new TreeNode(preorder[preindex]);
        // 找到根节点所在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preindex]);
        preindex++;
        // 先创建左树，再创建右树，本身是在遍历：前序遍历
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findIndex(int[] inorder,int inbegin,int inend,int key){
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
*/
    // 中序、后序遍历还原二叉树
    /*public  int postindex=0;
    public TreeNode buildTree(int[] inorder, int[] postOrder) {

        postindex=postOrder.length-1;
        return buildTreeChild(postOrder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] postOrder, int[] inorder,int inbegin,int inend){
        // 递归出口 不满足这个条件，就说明没有左右树了
        if(inbegin>inend){
            return null;
        }
        // 先创建根节点
        TreeNode root = new TreeNode(postOrder[postindex]);
        // 找到根节点所在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postOrder[postindex]);
        postindex++;
        // 先创建右树，再创建左树，本身是在遍历：后序遍历
        root.right = buildTreeChild(postOrder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postOrder,inorder,inbegin,rootIndex-1);
        return root;
    }
    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }*/
}
